package com.df.daatastructure.array;

public class ArrayQuestion {

    /**
     * --- 买卖股票的最佳时机 II
     *给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
     *
     * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
     *
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     *示例 1:
     *
     * 输入: [7,1,5,3,6,4]
     * 输出: 7
     * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     *      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
     *
     *示例 2:
     *
     * 输入: [1,2,3,4,5]
     * 输出: 4
     * 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     *      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     *      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
     *
     *示例 3:
     *
     * 输入: [7,6,4,3,1]
     * 输出: 0
     * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     *
     *提示：
     *
     * 1 <= prices.length <= 3 * 10 ^ 4
     * 0 <= prices[i] <= 10 ^ 4
     */

    public int question1_maxProfit(int[] prices){
        int maiIndex = 0;//标识买的索引
        int chuIndex = 1;//标识卖的索引
        int price = 0;//标识收益
        /**
         * 分析：
         * 买的时机：前一天比后一天的小，则前一天买，
         * 卖的时机：后续天中都要比买的时候大，且只能越来越大，如果碰到一个减小的，则把前一个大的天数卖
         */
        while (chuIndex<prices.length){//一直将卖索引后移，看买的和卖的天对应的值情况
            //此循环用于取出卖的时机：买的值要比卖的值小，且卖出的前一天的值也要小于卖出当天的值，则继续看下一天的值是否更大，如果当天小于前一天的，则卖出前一天的
            while (chuIndex<prices.length &&prices[maiIndex]<prices[chuIndex] &&prices[chuIndex-1]<prices[chuIndex] ){
                chuIndex++;
            }
            //如果卖出天值不是买的后一天，则正式买和卖并计算收益
            if(maiIndex+1!=chuIndex) {
                price += prices[chuIndex - 1] - prices[maiIndex];
            }
            //从新定位买和卖的索引
            maiIndex = chuIndex;
            chuIndex++;
        }
        return price;
    }

    /**
     * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
     *
     *示例 1:
     *
     * 输入: [1,2,3,4,5,6,7] 和 k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 解释:
     * 向右旋转 1 步: [7,1,2,3,4,5,6]
     * 向右旋转 2 步: [6,7,1,2,3,4,5]
     * 向右旋转 3 步: [5,6,7,1,2,3,4]
     *示例 2:
     *
     * 输入: [-1,-100,3,99] 和 k = 2
     * 输出: [3,99,-1,-100]
     * 解释:
     * 向右旋转 1 步: [99,-1,-100,3]
     * 向右旋转 2 步: [3,99,-1,-100]
     *说明:
     *
     * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
     * 要求使用空间复杂度为 O(1) 的 原地 算法。
     * https://leetcode-cn.com/problems/rotate-array/comments/
     */

    public void question2_rotate(int[] nums,int k){
//        方案一：依次向右移动
//             * 时间复杂度：O(kn)
//                * 空间复杂度：O(1)
//        k %=nums.length;
//        while (k>0){
//            int temp = 0;
//            temp = nums[nums.length-1];
//            for (int i = nums.length - 1; i > 0; i--) {
//                nums[i] = nums[i-1];
//            }
//            nums[0] = temp;
//            k--;
//        }

//        方案二：翻转
//             * 时间复杂度：O(n)
//                * 空间复杂度：O(1)
//        int n = nums.length;
//        k %= n;
//        reverse(nums, 0, n - 1);
//        reverse(nums, 0, k - 1);
//        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}
